package leetcode.秋招.字节跳动.字节研发在线编程;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/7/25 12:41
 * @description：https://www.nowcoder.com/practice/e3769a5f49894d49b871c09cadd13a61?tpId=190&&tqId=35214&rp=1&ru=/activity/oj&qru=/ta/job-code-high-rd/question-ranking
 */
public class NC93设计LRU缓存结构 {
    @Test
    public void test() {
    }


    public class Solution {
        /**
         * lru design
         * @param operators int整型二维数组 the ops
         * @param k int整型 the k
         * @return int整型一维数组
         */
        public int[] LRU (int[][] operators, int k) {
            // write code here
            LRUCache lruCache = new LRUCache(k);
            ArrayList<Integer> res = new ArrayList<>();
            for (int[] operator : operators) {
                if (operator[0] == 1) {
                    lruCache.put(operator[1], operator[2]);
                } else {
                    res.add(lruCache.get(operator[1]));
                }
            }
            int[] ans = new int[res.size()];
            for (int i = 0; i < res.size(); i++) {
                ans[i] = res.get(i);
            }
            return ans;
        }

        class LRUCache {
            int capacity;
            Map<Integer, Node> map;
            DoubleList list;

            public LRUCache (int cap) {
                this.capacity = cap;
                this.map = new HashMap<>();
                this.list = new DoubleList();
            }

            /**
             * 添加缓存
             * 如果map中包含当前key，则修改当前的val值，并将节点添加到链表头部
             * 否则
             *  如果双端链表的长度小于cap，直接添加到链表头部
             *  否则，移除链表最后一个节点，添加到链表头部，删除map中的映射
             *  最后，添加到map中
             * @param key
             * @param val
             */
            public void put(int key, int val) {
                Node cur = new Node(key, val);
                if(map.containsKey(key)) {
                    list.remove(map.get(key));
                    list.addFirst(cur);
                } else {
                    if(list.size == capacity) {
                        Node node = list.removeLast();
                        map.remove(node.key);
                    }
                    list.addFirst(cur);
                }
                map.put(key, cur);
            }

            /**
             * 如果map中不包含key，返回-1
             * 否则，获取当前节点，删除当前节点（map、list），将节点添加到list头部
             * @param key
             * @return
             */
            public int get(int key) {
                if(!map.containsKey(key)) return -1;
                Node target = map.get(key);
                list.remove(target);
                list.addFirst(target);
                return target.val;
            }
        }

        class Node {
            int key, val;
            Node next, pre;

            public Node(int key, int val) {
                this.key = key;
                this.val = val;
            }

            @Override
            public String toString() {
                return "Node{" +
                        "key=" + key +
                        ", val=" + val +
                        '}';
            }
        }

        class DoubleList {
            Node head;
            Node tail;
            int size;

            public DoubleList() {
                head = new Node(-1, -1);
                tail = new Node(-1, -1);
                head.next = tail;
                tail.pre = head;
                size = 0;
            }

            public void addFirst(Node node) {
                node.next = head.next;
                head.next = node;
                node.next.pre = node;
                node.pre = head;
                size++;
            }


            public Node remove(Node node) {
                node.pre.next = node.next;
                node.next.pre = node.pre;
                size--;
                return node;
            }

            public Node removeLast() {
                Node target = tail.pre;
                tail.pre.pre.next = tail;
                tail.pre = tail.pre.pre;
                size--;
                return target;
            }

            public void list() {
                Node temp = head.next;
                while(temp != tail) {
                    System.out.println(temp);
                    temp = temp.next;
                }
            }

        }
    }

    class LRUCache<K, V> extends LinkedHashMap<K, V> {
        private int CACHE_SIZE;

        public LRUCache(int cacheSize) {
            //true表示让hashmap按照访问顺序，最新访问的放在头部，最老访问的放在尾部
            super((int)Math.ceil(cacheSize / 0.75f) + 1, 0.75f, true);
            this.CACHE_SIZE = cacheSize;
        }
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            //当map中数量大于指定缓存数量，就删除最老的数据
            return size() > CACHE_SIZE;
        }
    }
}
